本场链接:Atcoder abc 174

闲话

本场F是个模板题,很谔谔.总体难度不高.

C.Repsept

题目大意:找一个最小的形如7777.....7777的数,使他是$k$的倍数.如果无解则输出-1,反之只需输出位数即可.

数据范围:
$1 \leq k \leq 10^6$

思路

显然线性复杂度暴力枚举,如果超过了某个迭代次数则认为无解.正确性是由于会出现循环节,假如次数足够多则必然可以保证确实是无解而没有答案的.而每次迭代的时候,如果本次的数字是$a$则下一次的数字就是$(a*10+7)$.直到$k|a$或次数过多停止.

代码

#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;

int main()
{
	int k;cin >> k;
	int a = 7,res = 0,ok = 1;
	while(a % k != 0)
	{
		a = (a * 10 + 7) % k;
		++res;
		if(res == 1e7 + 7)	break;
	}	
	if(a % k == 0)	cout << res+1;
	else cout << -1;
    return 0;
}

D.Alter Altar

题目大意:给定一个序列,要求每个R的左边不能是W.每次你可以执行两种操作中的一种,分别是交换序列里两个任意位置的元素,直接修改某个元素.问最少次数是多少,不需要具体方案.

思路

显然,最终要达到的情况形如RRRWWW.即所有的R都在左边,所有的W都在右边.由于每次交换都是任意的,所以直接统计所有的数量就可以知道把所有的R转移到最左边需要几次.由于直接修改的操作和交换事实上是对操作数量的影响是等价的,所以不需要管修改操作,只计算交换即可.

代码

#define _CRT_SECURE_NO_WARNINGS
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    string s;cin >> s;
    int cnt = 0;
    for(int i = 0;i < n;++i)	cnt += (s[i] == 'R');
    int res = 0;
    for(int i = 0;i < cnt;++i)
    {
    	if(s[i] == 'W')
    		++res;
    }	
    cout << res << endl;
    return 0;
}

E.Logs

题目大意:有$n$个木棍,他们的长度给定.你可以砍$K$次木棍,每次任选出一个木棍,并把他切成$t$和$L-t$两个长度,其中$t \in [0,L]$.问在进行$K$次之后,所有的木棍中最长的最小值是多少.计算出答案后,如果是小数,则向上取整并输出一个整数.

数据范围:
$1 \leq n \leq 2*10^5$
$0 \leq k \leq 10^9$
$1 \leq a_i \leq 10^9$

思路

想法非常明显,典型的二分答案.答案$\in [1,10^9]$.
考虑怎么写$check$.设当前的答案是$x$.如果$check$的真定义为所有木棍砍完之后的最大值$leq x$,则二分时如果为真,则应缩小范围,因为要最大值最小,既然这个$x$是可以取到的,那么就应该缩小范围,去找到一个可能的更小的值作为答案.这样整个框架也就确定了.对于$check$的条件判断来说,在里面遍历每一格根木棍的长度,要使最大值不超过$x$,也就是要确定一个长度为$L$的木棍最少要切几刀,这一点很显然就是看$L$里包含几个$x$,如果剩下的部分不足$x$,显然不需要考虑,这就是下取整,即需要砍$\lfloor\frac{L}{x}\rfloor$刀.最后看总刀数是不是$\leq k$的就可以了.

代码

const int N = 2e5+7;
const double eps = 1e-3;
int a[N],n,k;
bool check(double x)
{
	int res = 0;
	for(int i = 1;i <= n;++i)
	{
		res += floor(a[i] / x);
	}
	return res <= k;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= n;++i)	cin >> a[i];
	double l = 1,r = 1e9;
	while(r - l > eps)
	{
		double mid = (l + r) / 2;
		if(check(mid))	r = mid;
		else l = mid;
	}
	cout << (int)ceil(l);
    return 0;
}

F.Range Set Query

题目大意:多组区间查询不同数的个数.
数据范围:
$1 \leq N,Q \leq 5*10^5$
$1 \leq e_i \leq N$
$1 \leq l_i \leq r_i \leq N$

思路

莫队的模板题.如果不会莫队建议看这个博客,写的非常好.我在这里只简单说一下莫队算法是什么.
莫队本质上是在分块基础之上的,进一步的优化.首先是用两个指针表示当前查询的区间,并通过移动的方式更新当前的答案,其次再在离线的前提之下,将所有的查询进行排序,这样可以使指针的移动的次数处于一个比较稳定的状态.
还有一点,我的代码是没有卡常优化的,实际就差几十ms就TLE了.关于卡常也建议去看那个博客.加了优化之后大概快三倍左右.
我比赛的时候因为忘了空间开大导致WA了两发,就很蛋疼.

代码

const int N = 1e6+7;
int a[N],belong[N],cnt[N],res[N];
int quasize,bnum,now;
struct _Node
{
	int l,r,id;
	bool operator<(const _Node& b)	const
	{
		if(belong[l] == belong[b.l])	return r < b.r;
		return belong[l] < belong[b.l];
	}
}q[N];
inline void del(int pos)
{
	--cnt[a[pos]];
	if(!cnt[a[pos]])	--now;
}
inline void add(int pos)
{
	if(!cnt[a[pos]])	++now;
	++cnt[a[pos]];
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	quasize = sqrt(n);
	bnum = ceil(double(n) / quasize);
	
	for(int i = 1;i <= bnum;++i)
		for(int j = (i - 1) * quasize + 1;j <= i * quasize;++j)
			belong[j] = i;
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
	for(int i = 1;i <= m;++i)	scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
	sort(q+1,q+m + 1);
	
	int l = 1,r = 0;
	for(int i = 1;i <= m;++i)
	{
		int ql = q[i].l,qr = q[i].r;
		while(l < ql)	del(l++);
		while(l > ql)	add(--l);
		while(r < qr)	add(++r);
		while(r > qr)	del(r--);
		res[q[i].id] = now;
	}
	for(int i = 1;i <= m;++i)	printf("%d\n",res[i]);
	return 0;
}